package java_0305_sort;

/**
 * @author 美女
 * @date 2022/03/28 18:58
 **/

/**
 * 插入排序
 * 已排序区间[0,i)
 * 待排序区间[i,n]
 * 每次从无序区间中拿第一个值插入到排序区间的合适位置，直到数组有序
 */

public class InsertionSort {
    public static void insertionSort2(int[] arr){
        //外层遍历已排序区间；从第二个元素开始，默认第一个元素已排序
        for (int i = 1; i < arr.length ; i++) {
            //内层遍历未排序区间
            for (int j = i; j >0 ; j--) {
                if(arr[j]>arr[j-1]){
                    break;
                }else{
                    swap(arr,j,j-1);
                }
            }
        }
    }

    private static void swap(int[] arr, int j, int i) {
        int temp=arr[j];
        arr[j]=arr[i];
        arr[i]=temp;
    }
}
